import java.util.Arrays;

public class Review {

    /*public static void process(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];//辅助数组
        int p1 = l, p2 = mid + 1;//两个下标
        int i = 0;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];//谁小谁就放辅助数组并且自增
        }

        //事实上下面的两个while只可能运行一个
        while (p1 <= mid) {//把剩下的数字放在辅助数组里
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {//把剩下的数字放在辅助数组里
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {//辅助数组内容倒回原数组
            arr[l + i] = help[i];
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);//数组左半部分有序
        mergeSort(arr, mid + 1, r);//数组右半部分有序
        process(arr, l, mid, r);//左右有序之后，整体合并有序
    }

    public static void main(String[] args) {
        int[] arr = {2,7,5,8,1,99,58};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

     */

    /*
    public static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, res = 0;
        int i = 0;
        while (p1 <= mid && p2 <= r) {
            res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;//右边比左边大，右边剩余的都比他大
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) +
                process(arr, mid + 1, r) +
                merge(arr, l, mid,r );
        /*
        返回值是左边的小和 + 右边的小和 + 整体的小和
         */
    //}

    /*public static int smallSum(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {2,7,3,4,5,1};
        int res = smallSum(arr);
        System.out.println(res);
    }

     */

    public static int merge(int[] nums, int l, int mid, int r) {
        int p1 = l, p2 = mid + 1, res = 0, i = 0;
        int[] help = new int[r - l + 1];
        while ((p1 <= mid) && (p2 <= r)) {
            res += nums[p1] > (2 * nums[p2]) ? (mid - p1 + 1) : 0;
            help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
        }

        while (p1 <= mid) {
            help[i++] = nums[p1++];
        }
        while (p2 <= r) {
            help[i++] = nums[p2++];
        }
        for(i = 0; i<help.length;i++) {
            nums[l + i] = help[i];
        }
        return res;
    }

    public static int process(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >>> 1);
        return process(nums, l, mid) +
                process(nums, mid + 1, r) +
                merge(nums, l, mid, r);
    }

    public static int reversePairs(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int ret = process(nums, 0, nums.length - 1);
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,2,3,1};
        int ret = reversePairs(arr);
        System.out.println(ret);
        System.out.println(Arrays.toString(arr));
    }
}
